package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Puzzle implements Comparable{

    private int[] num = new int[25];
    //估计函数f(n)
    private int fn;
    //当前的深度/步骤d(n)
    private int dn;
    //到目标的最小估计(记录和目标状态有多少个数不同)h(n)
    private int hn;
    //父状态
    private Puzzle parent;

    static private ArrayList<Puzzle> answer = new ArrayList<>();    //保存最终路径


    public int[] getNum() {
        return num;
    }
    public void setNum(int[] num) {
        this.num = num;
    }
    public int getDn() {
        return dn;
    }
    public void setDn(int dn) {
        this.dn = dn;
    }
    public int getFn() {
        return fn;
    }
    public void setFn(int fn) {
        this.fn = fn;
    }
    public int getHn() {
        return hn;
    }
    public void setHn(int hn) {
        this.hn = hn;
    }
    public Puzzle getParent() {
        return parent;
    }
    public void setParent(Puzzle parent) {
        this.parent = parent;
    }

    //以f(n)排序
    @Override
    public int compareTo(Object o) {
        Puzzle c = (Puzzle) o;
        return this.fn -c.getFn();
    }

    public static void main(String[] args){
        ArrayList<Puzzle> open = new ArrayList<>();
        ArrayList<Puzzle> close = new ArrayList<>();
        Puzzle start = new Puzzle();
        Puzzle target = new Puzzle();

        // int[] startState = {12,14,11,9,17,13,16,1,2,5,22,24,6,21,4,7,18,19,15,23,0,3,20,10,8};
        // int[] endState = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,0};
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入初始状态：（以一维数组形式）");
        String[] arr = sc.next().split(",");
        int[] startState = new int[arr.length];
        for(int j=0;j<startState.length;j++)
            startState[j] = Integer.parseInt(arr[j]);
        System.out.println("请输入目标状态：（以一维数组形式）");
        arr = sc.next().split(",");
        int[] endState = new int[arr.length];
        for(int j=0;j<endState.length;j++)
            endState[j] = Integer.parseInt(arr[j]);
        s.close();

        start.setNum(startState);
        target.setNum(endState);
        if(start.isSolvable(target)){
            //初始化初始状态
            start.init(target);
            open.add(start);
            while(!open.isEmpty()){
                //按照fn排序
                Collections.sort(open);
                //从open表中取出最小估值的状态并移出open表
                Puzzle best = open.get(0);
                open.remove(0);
                close.add(best);

                if(best.isTarget(target)){
                    best.printRoute();
                    System.exit(0);
                }

                int move;
                //由best状态进行扩展并加入到open表中
                //0的位置上移之后状态不在close和open中设定best为其父状态，并初始化f(n)估值函数
                if(best.isMoveUp()){
                    move = 0;
                    Puzzle up = best.moveUp(move);//best的一个子状态
                    up.operation(open, close, best, target);
                }
                //0的位置下移之后状态不在close和open中设定best为其父状态，并初始化f(n)估值函数
                if(best.isMoveDown()){
                    move = 1;
                    Puzzle down = best.moveUp(move);
                    down.operation(open, close, best, target);
                }
                //0的位置左移之后状态不在close和open中设定best为其父状态，并初始化f(n)估值函数
                if(best.isMoveLeft()){
                    move = 2;
                    Puzzle left = best.moveUp(move);
                    left.operation(open, close, best, target);
                }
                //0的位置右移之后状态不在close和open中设定best为其父状态，并初始化f(n)估值函数
                if(best.isMoveRight()){
                    move = 3;
                    Puzzle right = best.moveUp(move);
                    right.operation(open, close, best, target);
                }

            }
        }else
            System.out.println("无解");
    }


    public void init(Puzzle target){
        //初始化hn
        int temp = 0;
        for(int i=0;i<25;i++){
            if(num[i]!=target.getNum()[i])
                temp++;
        }
        this.setHn(temp);
        //初始化dn
        if(this.getParent()==null){
            this.setDn(0);
        }else{
            this.dn = this.parent.getDn()+1;
        }
        //fn = dn + hn ;
        this.setFn(this.getDn()+this.getHn());
    }

    public boolean isTarget(Puzzle target){
        return Arrays.equals(getNum(), target.getNum());
    }


    public boolean isSolvable(Puzzle target){
        int reverse = 0;
        for(int i=0;i<25;i++){
            for(int j=0;j<i;j++){
                if(num[j]>num[i] && num[j]!=0 && num[i]!= 0)
                    reverse++;
                if(target.getNum()[j]>target.getNum()[i] && target.getNum()[j]!=0 && target.getNum()[i]!=0)
                    reverse++;
            }
        }
        return reverse % 2 == 0;
    }


    public int isContains(ArrayList<Puzzle> open){
        for(int i=0; i<open.size(); i++){
            if(Arrays.equals(open.get(i).getNum(), getNum())){
                return i;
            }
        }
        return -1;
    }


    public int getZeroPosition(){
        int position = -1;
        for(int i=0;i<25;i++){
            if(this.num[i] == 0){
                position = i;
            }
        }
        return position;
    }


    public boolean isMoveUp() {
        int position = getZeroPosition();
        return position > 4;
    }

    public boolean isMoveDown() {
        int position = getZeroPosition();
        return position < 20;
    }

    public boolean isMoveLeft() {
        int position = getZeroPosition();
        return position % 5 != 0;
    }

    public boolean isMoveRight() {
        int position = getZeroPosition();
        return (position) % 5 != 4;
    }

//    移动数码元素，探索下一步状态
    public Puzzle moveUp(int move){
        Puzzle temp = new Puzzle();
        temp.setNum(num.clone());
        int position = getZeroPosition();
        int p=0;
        switch(move){
            case 0:
                p = position-5;
                temp.getNum()[position] = num[p];
                break;
            case 1:
                p = position+5;
                temp.getNum()[position] = num[p];
                break;
            case 2:
                p = position-1;
                temp.getNum()[position] = num[p];
                break;
            case 3:
                p = position+1;
                temp.getNum()[position] = num[p];
                break;
        }
        temp.getNum()[p] = 0;
        return temp;
    }

//    处理列表open和close
    public void operation(ArrayList<Puzzle> open,ArrayList<Puzzle> close,Puzzle parent,Puzzle target){
        if(this.isContains(close) == -1){
            int position = this.isContains(open);
            if(position == -1){
                this.parent = parent;
                this.init(target);
                open.add(this);
            }else{
                if(this.getDn() < open.get(position).getDn()){
                    open.remove(position);
                    this.parent = parent;
                    this.init(target);
                    open.add(this);
                }
            }
        }
    }

//    输出结果
    public void printRoute(){
        Puzzle temp;
        int count = 0;
        temp = this;
        System.out.println("--------------------");
        while(temp!=null){
            answer.add(temp);
            temp = temp.getParent();
            count++;
        }
        for(Puzzle pz : answer){
            for(int i=0 ; i<25 ; i++){
                if(i%5 == 4){
                    System.out.println(pz.num[i]);
                }else{
                    System.out.print(pz.num[i]+"  ");
                }
            }
            System.out.println("--------------------");
        }
        System.out.println("最小移动步数："+(count-1));
    }

}